package 最大的和;

import java.util.Scanner;

public class Main {
    static int N = 50010;
    static int[] w = new int[N];
    static int[] f = new int[N];
    static int[] g = new int[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while (T-- > 0) {
            int n = in.nextInt();
            for (int i = 1; i <= n; i++) {
                w[i] = in.nextInt();
            }
            f[0] = g[n + 1] = -0x3f3f3f3f;
            for (int i = 1, s = 0; i <= n; i++) {
                s = w[i] + Math.max(s, 0);
                f[i] = Math.max(f[i - 1], s);
            }
            for (int i = n, s = 0; i >= 1; i--) {
                s = w[i] + Math.max(s, 0);
                g[i] = Math.max(g[i + 1], s);
            }
            int res = -0x3f3f3f3f;
            for (int i = 1; i <= n; i++) {
                res = Math.max(res, f[i] + g[i + 1]);
            }
            System.out.println(res);
        }
    }
}
